Cloud services have become an integral part of our lives as they promise a convenient means for users to access and store their data from multiple devices. The cloud also promises a cost-effective alternative for small and medium enterprises to offer their services without the need for huge upfront investments, e.g., to ensure high service availability.
Currently, most cloud storage services guarantee service and data availability in their Service Level Agreements, SLAs. Availability is typically ensured by means of full replication. Replicas are typically stored onto different servers, thus ensuring data availability in spite of server failure. Currently, storage services such as Amazon S3 and Google FS provide such resiliency against a maximum two concurrent failures; here, users are typically charged according to the required redundancy level.
Nevertheless, none of today's cloud providers accept any liability for data loss in their SLAs. This makes users reluctant when using cloud services due to concerns with respect to the integrity of their outsourced data. To remedy this, the literature features a number of solutions that enable users to remotely verify the integrity of stored data. Examples include Proofs of Retrievability, POR, see Shacham, H., and Waters, B. Compact Proofs of Retrievability, in ASIACRYPT (2008), pp. 90-107, which provide end-clients with the assurance that the data is available in its entirety, and Proofs of Data Possession, PDP, see Ateniese, G., Burns, R. C., Curtmola, R., Herring, J., Kissner, L., Peterson, Z. N. J., and Song, D. X. Provable data possession at untrusted stores, in ACM Conference on Computer and Communications Security (2007), pp. 598-609, which enable a client to verify that its stored data has not undergone any modifications, among others. These schemes have been recently extended to support the remote integrity verification of multi-replicas, MRV, see Curtmola, R., Khan, O., Burns, R. C., and Ateniese, G. MR-PDP: Multiple-Replica Provable Data Possession, in ICDCS (2008), pp. 411-420; MRV enables users to verify that they are getting the value of their money by verifying the replication status and the integrity of their replicated data. All existing MRV solutions share a similar system model, requiring the users themselves to create replicas of their files, appropriately pre-process the replicas, e.g., to create authentication tags, and finally store all processed replicas onto the cloud.